package Structure.MyLinkedList;

import java.util.function.Consumer;

/**
 * @author wang'ji'cheng
 * @date 2025/8/2
 * 带哨兵的单向链表
 */

public class SinglyLinkedListSentinel {


    //带哨兵的头结点
    private Node head = new Node(0, null);
    //大小
    private int size;


    public int getSize() {
        return this.size;
    }

    /**
     * 节点类
     */
    public static class Node {
        //值
        private Object value;
        //下一个指针
        private Node next;

        public Node(Object value, Node next) {
            this.value = value;
            this.next = next;
        }
        public Object getValue(){
            return this.value;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "value=" + value +
                    ", next=" + next +
                    '}';
        }
    }

    //头插法
    public void addFirst(Object value) {
        //不会出现头结点为空的情况，直接添加即可
        head.next = new Node(value, head.next);
        size++;
    }

    //遍历
    public void loop() {
        //头指针是哨兵，应该从下一个开始遍历
        Node p = head.next;
        Object value;
        while (p != null) {
            value = p.value;
            p = p.next;
            System.out.println(value);
        }

    }

    //for循环遍历
    public void forLoop() {

    }


    //尾插法
    public void addLast(Object value) {
        //获取最后一个节点
        Node last = getLast();
        last.next = new Node(value, null);
        size++;
    }

    //获取尾节点
    public Node getLast() {
        Node node = head;
        while (node.next != null) {
            node = node.next;
        }
        return node;
    }

    //遍历的通用写法
    public void loop2(Consumer<Integer> consumer) {

    }

    //根据索引获取元素的值
    public Object get(int index) {
        Node p = head.next;
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("size: " + size + "  index: " + index);
        } else {
            for (int i = 0; i < index; i++) {
                p = p.next;
            }
        }
        return p.value;
    }

    //获取节点
    public Node getNode(int index) {
        Node p = head.next;
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("size: " + size + "   index: " + index);
        } else {
            for (int i = 0; i < index; i++) {
                p = p.next;
            }
        }
        return p;
    }

    //插入节点
    public void insert(int index, Object value) {
        if (index == 0) {
            addFirst(value);
        } else if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("size: " + size + "   index: " + index);
        } else {
            Node node = head.next;
            for (int i = 0; i < index - 1; i++) {
                node = node.next;
            }
            node.next = new Node(value, node.next);
        }
        size++;
    }

    //删除节点
    public Node remove(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("size: " + size + "   index: " + index);
        }
        Node p = head;
        //获取被删除的前一个节点
        for (int i = 0; i < index; i++) {
            p = p.next;
        }
        Node toRemove = p.next;
        //被删除节点的后一个节点
        p.next = toRemove.next;
        toRemove.next = null;
        size--;
        return toRemove;
    }

}



